package 从中序与后序遍历序列构造二叉树;

public class Solution {
    /*
    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历
    postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 很容易想到使用递归解决
        // 1.参数：inorder，postorder，inorderBegin，inorderEnd，postorderBegin，postorderEnd
        // 返回值：左右子树的根节点，TreeNode
        // 2.终止条件：当出现postorderBegin >= postorderEnd 时结束，取 ”=“ 是因为我们采用的是左闭右开
        // 3.单层递归逻辑：首先根据后续遍历确定根节点，然后根据确认的节点，在中序遍历中确定该节点的左右子树。
        // 问题就是如何划分inorder和postorder的区间
        // 首先解决inorder的区间：只需要根据切割点的值就可以找到其在inorder中的索引位置
        // 其次解决postorder的区间：我们需要明白，在inorder中切割为两个区间之后，那么左区间节点个数，一定就是左子树节点个数，
        // 同理右区间也是。那么根据这一性质，我们就能够将postorder划分为 左后区间 / 右后区间，划分的依据就是每个区间的节点个数
        // 即：[ postorder.begin(), postorder.begin()+leftInorder.size()]
        // [ postorder.begin() + leftInorder.size(), postorder.end() ]

        // 左闭右开
        TreeNode root = buildTreeD(inorder, postorder,
                0, inorder.length,
                0, postorder.length);
        return root;
    }

    public TreeNode buildTreeD(int[] inorder, int[] postorder, int inorderBegin, int inorderEnd, int postorderBegin, int postorderEnd) {
        // 终止条件,取 ”=“ 是因为我们采用的是左闭右开
        if (inorderBegin >= inorderEnd || postorderBegin >= postorderEnd) {
            return null;
        }
        // 根据后序遍历确认根节点
        int postValue = postorder[postorderEnd - 1];
        // 构造该节点
        TreeNode root = new TreeNode(postValue);
        // 寻找切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < postorder.length; delimiterIndex++)
            // inorder 和 postorder 都由 不同 的值组成,所以只要找到相等的地方即可
            if (inorder[delimiterIndex] == postValue) {
                break;
            }
        // 递归构建左右子树，左闭右开
        int lenOfLeft = delimiterIndex - inorderBegin;
        root.left = buildTreeD(inorder, postorder,
                inorderBegin, delimiterIndex,
                postorderBegin, postorderBegin + lenOfLeft);
        root.right = buildTreeD(inorder, postorder,
                delimiterIndex + 1, inorderEnd,
                postorderBegin + lenOfLeft, postorderEnd - 1);
        return root;
    }
}
